Lucas–Lehmer primality test

This article is about the Lucas–Lehmer test that only applies to Mersenne numbers. For the Lucas–Lehmer test that applies to a natural number n, see Lucas primality test. For the Lucas–Lehmer–Riesel test, see Lucas–Lehmer–Riesel test.

In mathematics, the Lucas–Lehmer test (LLT) is a primality test for Mersenne numbers. The test was originally developed by Édouard Lucas in 1856,^[1] and subsequently improved by Lucas in 1878 and Derrick Henry Lehmer in the 1930s.

1 The test
2 Time complexity
3 Examples
4 Proof of correctness
- 4.1 Sufficiency
- 4.2 Necessity
5 Applications
6 See also
7 References
8 External links

The test

The Lucas–Lehmer test works as follows. Let M_p = 2^p − 1 be the Mersenne number to test with p an odd prime (because p is exponentially smaller than M_p, we can use a simple algorithm like trial division for establishing its primality). Define a sequence {s_i } for all i ≥ 0 by

$s_i= \begin{cases} 4 & \text{if }i=0; \\ s_{i-1}^2-2 & \text{otherwise.} \end{cases}$

The first few terms of this sequence are 4, 14, 194, 37634, ... (sequence A003010 in OEIS). Then M_p is prime iff

$s_{p-2}\equiv0\pmod{M_p}.$

The number s_p − 2 mod M_p is called the Lucas–Lehmer residue of p. (Some authors equivalently set s₁ = 4 and test s_p−1 mod M_p). In pseudocode, the test might be written:

// Determine if M_p = 2^p − 1 is prime
Lucas–Lehmer(p)
    var s = 4
    var M = 2^p − 1
    repeat p − 2 times:
        s = ((s × s) − 2) mod M
    if s = 0 return PRIME else return COMPOSITE

By performing the mod M at each iteration, we ensure that all intermediate results are at most p bits (otherwise the number of bits would double each iteration). It is exactly the same strategy employed in modular exponentiation.

Time complexity

In the algorithm as written above, there are two expensive operations during each iteration: the multiplication s × s, and the mod M operation. The mod M operation can be made particularly efficient on standard binary computers by observing the following simple property:

$k \equiv (k \hbox{ mod } 2^n) %2B \lfloor k/2^n \rfloor \pmod{2^n - 1}.$

In other words, if we take the least significant n bits of k, and add the remaining bits of k, and then do this repeatedly until at most n bits remain, we can compute the remainder after dividing k by the Mersenne number 2ⁿ−1 without using division. For example:

916 mod 2⁵−1	=	1110010100₂ mod 2⁵−1
	=	11100₂ + 10100₂ mod 2⁵−1
	=	110000₂ mod 2⁵−1
	=	1₂ + 10000₂ mod 2⁵−1
	=	10001₂ mod 2⁵−1
	=	10001₂
	=	17.

Moreover, since s × s will never exceed M² < 2^2p, this simple technique converges in at most 2 p-bit additions, which can be done in linear time. As a small exceptional case, the above algorithm may produce 2ⁿ−1 for a multiple of the modulus, rather than the correct value of zero; this should be accounted for.

With the modulus out of the way, the asymptotic complexity of the algorithm depends only on the multiplication algorithm used to square s at each step. The simple "grade-school" algorithm for multiplication requires O(p²) bit-level or word-level operations to square a p-bit number, and since we do this O(p) times, the total time complexity is O(p³). A more efficient multiplication method, the Schönhage–Strassen algorithm based on the Fast Fourier transform, requires O(p log p log log p) time to square a p-bit number, reducing the complexity to O(p² log p log log p) or Õ(p²).^[2]. Currently the most efficient known multiplication algorithm, Fürer's algorithm, needs $p \log p\ 2^{O(\log^* p)}$ time to multiply two p-bit numbers.

By comparison, the most efficient randomized primality test for general integers, the Miller–Rabin primality test, takes O(k p² log p log log p) bit operations using FFT multiplication for a p-digit number (here p can be any natural number, not necessarily a prime), where k is the number of iterations and is related to the error rate. So it is in the same complexity class as the Lucas-Lehmer test for constant k. But in practice the cost of doing many iterations and other differences leads to worse performance for Miller–Rabin. The most efficient deterministic primality test for general integers, the AKS primality test, requires Õ(p⁶) bit operations in its best known variant and is dramatically slower in practice.

Examples

Suppose we wish to verify that M₃ = 7 is prime using the Lucas–Lehmer test. We start out with s set to 4 and then update it 3−2 = 1 time, taking the results mod 7:

s ← ((4 × 4) − 2) mod 7 = 0

Because we end with s set to zero, M₃ is prime.

On the other hand, M₁₁ = 2047 = 23 × 89 is not prime. To show this, we start with s set to 4 and update it 11−2 = 9 times, taking the results mod 2047:

s ← ((4 × 4) − 2) mod 2047 = 14
s ← ((14 × 14) − 2) mod 2047 = 194
s ← ((194 × 194) − 2) mod 2047 = 788
s ← ((788 × 788) − 2) mod 2047 = 701
s ← ((701 × 701) − 2) mod 2047 = 119
s ← ((119 × 119) − 2) mod 2047 = 1877
s ← ((1877 × 1877) − 2) mod 2047 = 240
s ← ((240 × 240) − 2) mod 2047 = 282
s ← ((282 × 282) − 2) mod 2047 = 1736

Because s is not zero, M₁₁=2047 is not prime. Notice that we learn nothing about the factors of 2047, only its Lucas–Lehmer residue, 1736.

Proof of correctness

Lehmer's original proof of the correctness of this test is complex, so we'll depend upon more recent refinements. Recall the definition:

$s_i= \begin{cases} 4 & \text{if }i=0; \\ s_{i-1}^2-2 & \text{otherwise.} \end{cases}$

Then our theorem is that M_p is prime iff $s_{p-2}\equiv0\pmod{M_p}.$

We begin by noting that ${\langle}s_i{\rangle}$ is a recurrence relation with a closed-form solution. Define $\omega = 2 %2B \sqrt{3}$ and $\bar{\omega} = 2 - \sqrt{3}$ ; then we can verify by induction that $s_i = \omega^{2^i} %2B \bar{\omega}^{2^i}$ for all i:

$s_0 = \omega^{2^0} %2B \bar{\omega}^{2^0} = (2 %2B \sqrt{3}) %2B (2 - \sqrt{3}) = 4.$

$\begin{array}{lcl}s_n & = & s_{n-1}^2 - 2 \\ & = & \left(\omega^{2^{n-1}} %2B \bar{\omega}^{2^{n-1}}\right)^2 - 2 \\ & = & \omega^{2^n} %2B \bar{\omega}^{2^n} %2B 2(\omega\bar{\omega})^{2^{n-1}} - 2 \\ & = & \omega^{2^n} %2B \bar{\omega}^{2^n}, \\ \end{array}$

where the last step follows from $\omega\bar{\omega} = (2 %2B \sqrt{3})(2 - \sqrt{3}) = 1$ . We will use this in both parts.

Sufficiency

In this direction we wish to show that $s_{p-2}\equiv0\pmod{M_p}$ implies that $M_p$ is prime. We relate a straightforward proof exploiting elementary group theory given by J. W. Bruce^[3] as related by Jason Wojciechowski.^[4]

Suppose $s_{p-2} \equiv 0 \pmod{M_p}$ . Then $\omega^{2^{p-2}} %2B \bar{\omega}^{2^{p-2}} = kM_p$ for some integer k, and:

$\begin{align} \omega^{2^{p-2}} & = kM_p - \bar{\omega}^{2^{p-2}} \\ \left(\omega^{2^{p-2}}\right)^2 & = kM_p\omega^{2^{p-2}} - (\omega\bar{\omega})^{2^{p-2}} \\ \omega^{2^{p-1}} & = kM_p\omega^{2^{p-2}} - 1.\quad\quad\quad\quad\quad(1) \end{align}$

Now suppose M_p is composite, and let q be the smallest prime factor of M_p. Since Mersenne numbers are odd, we have q > 2. Define the set $X = \{a %2B b\sqrt{3} | a, b \in \mathbb{Z}_q\}$ with q² elements, where $\mathbb{Z}_q$ is the integers mod q, a finite field (in the language of ring theory X is the quotient of the univariate polynomial ring $\mathbb{Z}_q[T]$ by the ideal generated by $(T^2 - 3)$ ). The multiplication operation in $X$ is defined by:

$(a %2B b\sqrt{3})(c %2B d\sqrt{3}) = [(ac %2B 3bd) \hbox{ mod } q] %2B [(bc %2B ad) \hbox{ mod } q]\sqrt{3}.$

Since q > 2, $~ \omega$ and $\bar{\omega}$ are in $X$ (in fact $\omega%2B (T^2 - 3), \bar{\omega}%2B (T^2 - 3)$ are in X, but by abuse of language we identify $~ \omega$ and $\bar{\omega}$ with their images in X under the natural ring homomorphism from $\mathbb{Z}[\sqrt{3}]$ to X which sends the square root of 3 to T). Any product of two numbers in X is in X, but it's not a group under multiplication because not every element x has an inverse y such that xy = 1 (in fact X is a ring and the set of non-zero elements of X is a group if and only if $\mathbb{Z}_q$ does not contain a square root of 3). If we consider only the elements that have inverses, we get a group X* of size at most $q^2-1$ (since 0 has no inverse).

Now, since $M_p \equiv 0 \pmod q$ , and $\omega \in X$ , we have $kM_p\omega^{2^{p-2}} = 0$ in X, which by equation (1) gives $\omega^{2^{p-1}} = -1$ . Squaring both sides gives $\omega^{2^p} = 1$ , showing that $\omega$ is invertible with inverse $\omega^{2^{p}-1}$ and so lies in X*, and moreover has an order dividing $2^p$ . In fact the order must equal $2^p$ , since $\omega^{2^{p-1}} \neq 1$ and so the order does not divide $2^{p-1}$ . Since the order of an element is at most the order (size) of the group, we conclude that $2^p \leq q^2 - 1 < q^2$ . But since q is the smallest prime factor of the composite $M_p$ , we must have $q^2 \leq M_p = 2^p-1$ , yielding the contradiction $2^p < 2^p-1$ . So $M_p$ is prime.

Necessity

In the other direction, we suppose $M_p$ is prime and show $s_{p-2} \equiv0\pmod{M_p}$ . We rely on a simplification of a proof by Öystein J. R. Ödseth.^[5] First, notice that 3 is a quadratic non-residue mod M_p, since 2^p − 1 for odd p > 1 only takes on the value 7 mod 12, and so the Legendre symbol properties tell us $(3|M_p)$ is −1. Euler's criterion then gives us:

$3^{(M_p-1)/2} \equiv -1 \pmod{M_p}.\,$

On the other hand, 2 is a quadratic residue mod $M_p$ , since $2^p \equiv 1 \pmod{M_p}$ and so $2 \equiv 2^{p%2B1} = \left(2^{(p%2B1)/2}\right)^2 \pmod{M_p}$ . Euler's criterion again gives:

$2^{(M_p-1)/2} \equiv 1 \pmod{M_p}.\,$

Next, define $\sigma = 2\sqrt{3}$ , and define X* similarly as before as the multiplicative group of $\{a %2B b\sqrt{3} | a, b \in \mathbb{Z}_{M_p}\}$ . We will use the following lemmas:

$(x%2By)^{M_p} \equiv x^{M_p} %2B y^{M_p} \pmod{M_p}$

(from Proofs of Fermat's little theorem#Proof_using_the_binomial_theorem)

$a^{M_p} \equiv a \pmod{M_p}$

for every integer a (Fermat's little theorem)

Then, in the group X* we have:

$\begin{align} (6%2B\sigma)^{M_p} & = 6^{M_p} %2B (2^{M_p})(\sqrt{3}^{M_p}) \\ & = 6 %2B 2(3^{(M_p-1)/2})\sqrt{3} \\ & = 6 %2B 2(-1)\sqrt{3} \\ & = 6 - \sigma. \end{align}$

We chose $\sigma$ such that $\omega = (6%2B\sigma)^2/24$ . Consequently, we can use this to compute $\omega^{(M_p%2B1)/2}$ in the group X*:

$\begin{align} \omega^{(M_p%2B1)/2} & = (6 %2B \sigma)^{M_p%2B1}/24^{(M_p%2B1)/2} \\ & = (6 %2B \sigma)^{M_p}(6 %2B \sigma)/(24 \times 24^{(M_p-1)/2}) \\ & = (6 - \sigma)(6 %2B \sigma)/(-24) \\ & = -1. \end{align}$

where we use the fact that

$24^{(M_p-1)/2} = (2^{(M_p-1)/2})^3(3^{(M_p-1)/2}) = (1)^3(-1) = -1.$

Since $M_p \equiv 3 \pmod 4$ , all that remains is to multiply both sides of this equation by $\bar{\omega}^{(M_p%2B1)/4}$ and use $\omega\bar{\omega}=1$ :

$\begin{align} \omega^{(M_p%2B1)/2}\bar{\omega}^{(M_p%2B1)/4} & = -\bar{\omega}^{(M_p%2B1)/4} \\ \omega^{(M_p%2B1)/4} %2B \bar{\omega}^{(M_p%2B1)/4} & = 0 \\ \omega^{(2^p-1%2B1)/4} %2B \bar{\omega}^{(2^p-1%2B1)/4} & = 0 \\ \omega^{2^{p-2}} %2B \bar{\omega}^{2^{p-2}} & = 0 \\ s_{p-2} & = 0. \end{align}$

Since s_p−2 is an integer and is zero in X*, it is also zero mod M_p.

Applications

The Lucas–Lehmer test is the primality test used by the Great Internet Mersenne Prime Search to locate large primes, and has been successful in locating many of the largest primes known to date.^[6] The test is considered valuable because it can provably test a very large number for primality within affordable time and, in contrast to the equivalently fast Pépin's test for any Fermat number, can be tried on a large search space of numbers with the required form before reaching computational limits.

References

^ The Largest Known Prime by Year: A Brief History
^ Colquitt, W. N.; Welsh, L., Jr. (1991), "A New Mersenne Prime", Mathematics of Computation 56 (194): 867–870, "The use of the FFT speeds up the asymptotic time for the Lucas–Lehmer test for M_p from O(p³) to O(p² log p log log p) bit operations."
^ J. W. Bruce (1993). "A Really Trivial Proof of the Lucas–Lehmer Test". The American Mathematical Monthly 100 (4): 370–371.
^ Jason Wojciechowski. Mersenne Primes, An Introduction and Overview. 2003.
^ Öystein J. R. Ödseth. A note on primality tests for N = h · 2ⁿ − 1. Department of Mathematics, University of Bergen.
^ What are Mersenne primes? How are they useful? Frequently Asked Questions. GIMPS Home Page.

Crandall, Richard; Pomerance, Carl (2001), "Section 4.2.1: The Lucas–Lehmer test", Prime Numbers: A Computational Perspective (1st ed.), Berlin: Springer, p. 167–170, ISBN 0387947779

External links

Weisstein, Eric W., "Lucas–Lehmer test" from MathWorld.
GIMPS (The Great Internet Mersenne Prime Search)
A proof of Lucas–Lehmer–Reix test (for Fermat numbers)
Lucas–Lehmer test at MersenneWiki

Number-theoretic algorithms

Primality tests	AKS · APR · Baillie–PSW · ECPP · Elliptic curve · Pocklington · Fermat · Lucas · Lucas–Lehmer · Lucas–Lehmer–Riesel · Proth's theorem · Pépin's · Solovay–Strassen · Miller–Rabin · Trial division

Sieving algorithms	Sieve of Atkin · Sieve of Eratosthenes · Sieve of Sundaram · Wheel factorization

Integer factorization algorithms	CFRAC · Dixon's · ECM · Euler's · Pollard's rho · p − 1 · p + 1 · QS · GNFS · SNFS · rational sieve · Fermat's · Shanks' square forms · Trial division · Shor's

Multiplication algorithms	Ancient Egyptian multiplication · Karatsuba algorithm · Toom–Cook multiplication · Schönhage–Strassen algorithm · Fürer's algorithm

Discrete logarithm algorithms	Baby-step giant-step · Pollard rho · Pollard kangaroo · Pohlig–Hellman · Index calculus · Function field sieve

GCD algorithms	Binary GCD · Euclidean · Extended Euclidean · Lehmer's

Modular square root algorithms	Cipolla · Pocklington's · Tonelli–Shanks

Other algorithms	Chakravala · Cornacchia · integer relation algorithm · integer square root · Modular exponentiation · Schoof's

Italics indicate that algorithm is for numbers of special forms; bold indicates deterministic algorithm for primality tests (current article is always in bold).